ScienceDirect - Компьютерные Сети: маршрутизация Междомена: Алгоритмы для гарантий QoS

Samphel Norden ^,

Прозрачная Bell Labs, Комната 4F-529, 101 Угловая Дорога Crawfords, Holmdel, Нью-Джерси 07733, США

Полученный 16 марта 2004; пересмотренный 16 ноября 2004; принятый 28 января 2005. Ответственный Редактор: E. Ekici. Доступный онлайн 23 марта 2005.

1. Введение

Потребность в своевременной поставке информации в реальном времени по локальным и глобальным сетям больше распространена из-за быстрого расширения интернет-пользовательского населения в последние годы, и растущего интереса в использовании Интернета для телефонии, видео конференц-связи и других приложений мультимедиа. Выбирание маршрута, который встречает потребности ресурса таких приложений, является основным для условия обслуживания высокого качества это, пользователи приезжают, чтобы ожидать.

В этом контексте важно отличить маршрутизация потока и датаграмма. В датаграммной маршрутизации пакеты сеанса могут следовать за различными путями адресату. В маршрутизации потока все пакеты, принадлежащие прикладному сеансу, следуют за тем же самым путем, позволяя пропускную способность быть сохраненными вдоль того пути, чтобы гарантировать высокое качество обслуживания. Поскольку много тысяч или даже миллионы пакетов типично посылают во время единственного прикладного сеанса, маршрутизация потока происходит намного менее часто чем датаграммная маршрутизация, делая это практический, чтобы применить более сложные процедуры решения, чем может использоваться в датаграммной маршрутизации.

Текущий Интернет следует за датаграммой, направляющей модель, и полагается на адаптивное управление скопления, чтобы справиться с перегрузками. Интернет-трафик отправлен на основе лучшего усилия без гарантий работы. Это может привести к широким изменениям в работе, приводящей к плохому сервисному качеству для приложений, таких как голос и видео. Кроме того, интернет-маршрутизация типично управляема топологией вместо того, чтобы быть управляемой загрузкой. Этот подход не позволяет трафику быть направленным вдоль альтернативных путей, когда первичный маршрут адресату становится перегруженным. В то время как приложение чувствительной к загрузке маршрутизации к датаграммному трафику может вызвать трудные к управлению колебания трафика, это может быть успешно применено, чтобы течь, направляя, так как у сохраненных сеансов пропускных способностей типично есть времена занятости минут, эффективно заглушая любые быстрые колебания в маршрутах. Отметьте, что использование термина "поток" в остальной части этой бумаги также относится к совокупностям меньших "микропотоков", которые часто связываются, направляя через домены.

Самый видный междомен, направляющий протокол в текущем Интернете, является Протоколом Шлюза Границы (ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ) [1]. ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ - вектор пути базируемый протокол, где путь обращается к последовательности промежуточных доменов между маршрутизаторами адресата и источником. ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ страдает от многих хорошо зарегистрированных проблем, включая долгие времена конвергенции [2] и [3] после отказов ссылки. ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ принимает политику, базируемую, направляя механизм, посредством чего каждый домен применяет местную политику, чтобы выбрать лучший маршрут и решить, размножить ли этот маршрут к соседним доменам, не обнародуя их политику и топологию другим.

Непосредственный эффект политики базировался, подход должен потенциально ограничить возможные пути между каждой парой интернет-хостов. ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ не гарантирует, что каждая пара хостов может общаться даже при том, что там может существовать правильный путь между хостами. Кроме того, так как каждому домену позволяют использовать его собственную политику, чтобы определить маршруты, заключительный результат может быть путем, который в местном масштабе оптимален в некоторых доменах, но глобально подоптимален из-за нехватки однородной политики, или метрика имела обыкновение находить непрерывный маршрут. Этот пункт подсвечен [4] и [5], где большинство путей, которые выбраны ПОГРАНИЧНЫМ МЕЖСЕТЕВЫМ ПРОТОКОЛОМ, не представляет оптимальные непрерывные пути. Авторы определяют “оптимальные пути” счетом перелета в [4]. Их показ результатов, что для 50 % путей ПОГРАНИЧНОГО МЕЖСЕТЕВОГО ПРОТОКОЛА, там существует дополнительный путь с по крайней мере 5 меньше перелетов. В [5], различные меры качества пути, такие как норма потери, пропускная способность и время туда и обратно, последовательно указывают, что у 30-80 % путей фактически есть дополнительный путь со значительно превосходящим качеством чем путь значения по умолчанию, выбранный ПОГРАНИЧНЫМ МЕЖСЕТЕВЫМ ПРОТОКОЛОМ.

sub-optimality ПОГРАНИЧНОГО МЕЖСЕТЕВОГО ПРОТОКОЛА происходит прежде всего из-за большинства доменов, не выполняющих своих обязательств к маршрутизации злободневной политической проблемы, в который каждый домен в непрерывном пути, попытки шунтировать пакеты как можно быстрее к следующей сети в пути, а не маршрутам выбора, которые произведут лучшую непрерывную работу для пользователей. Эта характеристика ясно нежелательна, даже для датаграммного трафика, и особенно проблематична для сеансов, которые требуют высокого качества обслуживания. Таким образом, есть ясно критическая потребность в QoS маршрутизация механизма, который позволяет гарантии через домены.

Большинство исследования в маршрутизации QoS сосредоточилось на том, чтобы направлять в пределах единственного домена. В то время как проблема внутридомена важна, возможно еще более важно обратиться к QoS маршрутизация проблемы на уровне междомена. Кроме того, не выполнимо непосредственно расширить протоколы для маршрутизации внутридомена к контексту междомена. В то время как масшабируемость - еще большее беспокойство из-за явного числа узлов и доменов, проблема всматривающихся отношений может ограничить природу и периодичность информации, обмененной между доменами. Принимая во внимание, что, протокол внутридомена работает в меньшей сети, где все маршрутизаторы сотрудничают таким образом, что информация обо всей топологии может быть передана каждому маршрутизатору, это не возможно, направляя через домены. Обеспечение маршрутов QoS через домены сделано более трудным фактом, что у каждого домена есть ограничение на информацию, которую это обменивает с другими доменами. Это может затронуть маршруты, которые рекламируются динамиками ПОГРАНИЧНОГО МЕЖСЕТЕВОГО ПРОТОКОЛА и могут также изолировать домены даже при том, что правильные пути существуют между ними. Таким образом, есть потребность, чтобы развить QoS направляющие подходы, которые назад совместимы с текущими сетями, используя простые механизмы, чтобы избежать проблем масшабируемости и облегчить развертывание.

Новый междомен QoS, направляющий подход: Мы начинаем с наблюдения, что всматривающиеся ссылки, которые подключают отличные домены маршрутизации, типично являются первичными пунктами скопления или узкими местами для сетевого трафика [6].¹ Управлений использованием ресурса в таких пунктах скопления ясно важны по отношению к обеспечению непрерывного качества обслуживания.

У нашей стратегии для маршрутизации междомена есть две части. В части междомена свободный источник route ² отобран маршрутизатором в пункте происхождения сеанса. Этот исходный маршрут определяет домены, через которые должен пройти маршрут, и всматривающиеся ссылки имели обыкновение проходить от одного домена до следующего. В пределах каждого домена пути отобраны между входом и пунктами выхода, используя проблемно-ориентированную политику маршрутизации. Это упоминается как часть внутридомена. Это разложение непрерывной проблемы маршрутизации уважает право каждого домена поддержать частную жизнь его внутренней сетевой конфигурации и соответственно ограничивает количество информации, которая должна быть принята во внимание, когда выбор направляет. В то же самое время, это позволяет крупномасштабным характеристикам маршрута быть отобранными с соответствующим рассмотрением состояния всматривающихся ссылок.

Проблемы частной жизни: В то время как это может казаться нарушением частной жизни, чтобы распространить всматривающуюся информацию ссылки, мы полагаем, что это находится в лучшем интересе провайдера с несколькими выгодными последствиями. Например, предоставление информации о хронически влажной всматривающейся ссылке может смягчить загрузку на той ссылке. Балансирование загрузки не только увеличивает QoS клиенту, но также и создает больше дохода к участвующим провайдерам (на непрерывном пути), так как они теперь в состоянии нести больше запросов с меньшей вероятностью отклонения. Мы обсуждаем это более подробно в Разделе 6.

Проблемы масшабируемости: С любым QoS интригует маршрутизация, масшабируемость - важные критерии. В терминах реальной среды с тысячами автономных систем очевидно будут серьезные проблемы масштабирования, если вся всматривающаяся информация ссылки должна быть распространена. Мы обсуждаем эту проблему и ее потенциальное решение более подробно в Разделе 6.

Вклады: В этой газете мы предлагаем и оцениваем два междомена QoS маршрутизация алгоритмов, которые следуют за стратегией улучшающейся работы, избегая узкого места, всматривающегося ссылки. Мы начинаем, описывая простую оверлейную архитектуру сети, чтобы допустить QoS маршрутизация механизмов таким образом, что никакое изменение не необходимо для существующих механизмов, таких как ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ. Первое, использует довольно обычную структуру самого короткого пути, используя метрику стоимости, которая составляет и свойственную стоимость каждой ссылки и количество пропускной способности, которую ссылка имеет в наличии для использования. Второе динамически исследует несколько путей параллельно, чтобы найти путь способным к обрабатыванию потока. Этот подход избавляет от необходимости регулярные обновления маршрутизации, начиная с маршрутизации информации получен по требованию. Мы выполняем обширные эксперименты на реалистической топологии внутридомена и междомена, чтобы продемонстрировать существенные льготы, которые могут быть достигнуты при использовании наших предложенных схем.

Есть существенное количество предшествующего исследования в области внутридомена маршрутизация QoS. Однако, критерии дизайна для междомена маршрутизация QoS отличаются от маршрутизации внутридомена, со специальным акцентом на масшабируемости. Есть врожденный обмен между работой и масшабируемостью. Мы полагаем, что это - одна из первых бумаг, которая экстенсивно оценивает работу QoS маршрутизация протоколов и в intra и в контексте междомена и количественно оценивает обмен.

Схема бумаги следующие. Раздел 2 мотивирует и описывает два QoS маршрутизация алгоритмов, которые расширены для маршрутизации междомена. Работа этих алгоритмов маршрутизации в установке внутридомена также представлена, чтобы продемонстрировать их льготы. Раздел 3 расширяет эти алгоритмы, чтобы поддержать междомен QoS. Раздел 4 описывает окружающую среду моделирования междомена, и всесторонняя оценка работы алгоритмов маршрутизации, включая сравнение с ПОГРАНИЧНЫМ МЕЖСЕТЕВЫМ ПРОТОКОЛОМ базировала подход. Раздел 5 увеличивает QoS маршрутизация алгоритмов, чтобы облегчить развертывание в текущих сетях. Детали выполнения наряду с накладными расходами обработки развертывания предложенных алгоритмов представлены в Разделе 6. Раздел 7 представляет предшествующее исследование в области, и бумага заканчивается в Разделе 8.

2. Мотивация нового QoS маршрутизация алгоритмов

Чтобы гарантировать самую лучшую работу в присутствии полного диапазона условий трафика, для выбора маршрута важно вестись знанием текущей сетевой государственной информации, используя метрики, такие как потеря, время ожидания и доступная способность ссылки. Доступная пропускная способность в особенности особенно важна на уровне междомена, где всматривающиеся узкие места ссылки важны в определении, достигает ли пакет адресата. В этой газете мы сосредотачиваемся на том, чтобы использовать доступную пропускную способность как метрику для маршрутизации QoS. В этом разделе мы вводим два QoS маршрутизация алгоритмов, которые являются представительными для различных классов маршрутизации алгоритмов, которые колеблются от маршрутизации основанного на самом коротком алгоритме пути Dijkstra’s, используя link-state/distance векторные обновления, к динамическому по требованию исследование через многопутевую маршрутизацию.

Предыдущие сравнительные исследования продемонстрировали, что алгоритмы, которые рассматривают длину пути в решении маршрутизации, превосходят, которые не делают [7] и [8]. Само-самый короткий алгоритм пути ломает связи между маршрутами с той же самой длиной пути, выбирая путь с наибольшей доступной пропускной способностью узкого места. Однако неминимальные алгоритмы маршрутизации, такие как распределенный само-самый широкий путь часто выбирают окольные маршруты, которые потребляют дополнительные сетевые ресурсы за счет будущих сеансов, которые могут увеличить блокирование сеанса. Смещение к более коротким маршрутам пути особенно привлекательно в большой распределенной сети, так как длина пути - относительно устойчивая метрика по сравнению с динамическими измерениями задержки ссылки или нормы потери. Очень немного схем однако считают оба длиной пути так же как пропускной способностью в решении маршрутизации. Мы предлагаем Наименее объединенную Метрику Стоимости как метрику стоимости, которая объединяет оба длина пути так же как пропускная способность в эффективный механизм выбора маршрута. Большинству предыдущих подходов государства ссылки строго ослабляют "плохие" маршруты, выбранные из-за неправильной государственной информации. Наши факторы схемы в переутомлении государства ссылки, и соответственно веса связываются, чтобы свернуть возможность выбирания "плохих" маршрутов.

Однако, врожденный недостаток протоколов государства ссылки возможности использования информации государства устаревшей ссылки [9] все еще существует и может препятствовать выбору "оптимального" пути. Таким образом, есть потребность в протоколах, которые используют современное динамическое государство в выборе маршрута. Это приводит нас к по требованию исследованию использующих многопутевых алгоритмов маршрутизации.

Несколько многопутевых алгоритмов маршрутизации были предложены как альтернативы единственной маршрутизации пути. Большинство этих схем использует некоторую форму наводнения на основе в сеанс, помещая большую загрузку в оба маршрутизаторы так же как сеть. Хотя последующие схемы уменьшают наводнение, есть все еще существенное верхнее, так же как задержка установки маршрута. Дополнительно, большинство этих ресурсов запаса подходов в передовом передает по многократным путям, которые могут привести к блокированию других сеансов.

Основываясь на гибридных многопутевых подходах маршрутизации, мы предлагаем простую схему, названную параллельным алгоритмом исследования, у которого есть следующие особенности: (1) предвычисляет и кэширует ограниченное число замены equivalent³ пути между источником и адресатом так, чтобы маршрутизаторы не выполнили вычисление маршрута по требованию, значительно уменьшая маршрутизацию наверху и уход от любого наводнения; (2) посылает исследования на этих эквивалентных путях, по требованию позволяющих исследования собрать точную, современную информацию о ссылках для выбора маршрута, не резервируя ресурсы, таким образом уменьшая уверенность относительно информации устаревшей ссылки. Никакое государство не установлено исследованиями, который позволяет маршрутизатору быстрого пути, отправляющему, не блокируя посреднических ресурсов.

Источник против маршрутизации перелета перелетом: В то время как выполнимо использовать маршрутизацию перелета перелетом пакетов для гарантий QoS, классифицируя пакеты соответственно (например, IP область TOS, или Diffserv DS Байт), и поддерживая различные посылаемые таблицы для каждого класса пакетов. Протокол перелета перелетом также легче принять в текущем Интернете, так как текущие подходы маршрутизации (OSPF, ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ) используют механизм выбора перелета перелетом. Однако, подход перелета перелетом может выбрать местный перелет оптимально, но из-за нехватки знания характеристик пути вниз по течению, подключение могло быть отклонено. Мы сосредотачиваемся на явно направленных путях, так как легче обеспечить гарантируемый QoS на уровне потока, для пути с сохраненными ресурсами, чем с пакетом перелета перелетом, направляющим парадигму.

Мы теперь опишем обобщенные версии опорной линии нового QoS маршрутизация алгоритмов, которые работают в окружающей среде внутридомена. Мы представляем результаты моделирования на реалистической топологии внутридомена, показывающей льготам предложенных протоколов.

2.1. Наименее Объединенная Стоимость, Направляющая (LCC)

Наименее объединенная Стоимость, Направляющая (LCC) алгоритм, является алгоритмом государства ссылки, основанным на OSPF-TE [10]. Обновление государства ссылки предоставляет информацию о пропускной способности, доступной для использования сохраненными потоками пропускной способности, на всех ссылках в сети. Это позволяет каждому оверлейному узлу или маршрутизатору создавать полное представление сетевого состояния, которое может использоваться в принятии решений маршрутизации. Для остальной части этой бумаги термин "оверлейный узел" использован синонимично с "маршрутизатором". LCC направляет резервирование потока выбором наименее путь стоимости адресату, в исходном маршрутизаторе, где запрос резервирования сначала вводит сеть, затем ускоряя запрос резервирования вдоль этого пути, резервируя ресурсы при каждом перелете. Если в некоторый момент на пути, у отобранной ссылки нет достаточной способности для резервирования, то резервирование отклонено.

Метрика стоимости, используемая в вычислении пути, принимает во внимание и расстояния, заполненные ссылками и количество доступной пропускной способности относительно пропускной способности резервирования. Метрика стоимости мотивирована наблюдением, что всякий раз, когда сеть слегка загружена, пути должны быть отобраны, чтобы свернуть сумму свойственных затрат ссылки, так как это свертывает стоимость сетевых ресурсов, используемых, и сетевой задержки. Когда некоторые ссылки тяжело загружены, мы хотим регулировать трафик далеко от тех ссылок, даже если наша новая информация государства ссылки указывает, что у них есть достаточная способность обработать резервирование потока, являющееся установкой. Причина для ухода от таких ссылок - то, что во время начиная с последнего обновления государства ссылки, ссылка, возможно, стала слишком занятой, чтобы обработать резервирование. Вместо того, чтобы рисковать устанавливать резервирование на пути с высокой вероятностью отказа, мы предпочли бы более длинный путь с меньшим шансом отказа.

Таблица 1 список, которые несколько основных частей примечания, используемого в ссылке, стоят выражению, которому показывают, ниже которого упоминается как Объединенная Метрика Стоимости (CCM).

Таблица 1.
Примечание для метрики стоимости

Срок Объяснение

B Доступная пропускная способность на ссылке

R Пропускную способность резервирования требуют

L [u, v] Длина (расстояние) пути, присоединяющегося к маршрутизаторам u и v

М. Пропускная способность "край", где М. = B − R

Срок	Объяснение
B	Доступная пропускная способность на ссылке
R	Пропускную способность резервирования требуют
L [u, v]	Длина (расстояние) пути, присоединяющегося к маршрутизаторам u и v
М.	Пропускная способность "край", где М. = B − R

Эти три параметра, альфа, beta и г, определяют, как стоимость тяжело загруженной ссылки увеличивается. Определенно, если край ссылки (количество доступной пропускной способности, остающейся после вычитания пропускной способности, требуемой резервированием), больше чем г, то стоимость ссылки равна ее длине. Если его край - меньше чем пороговый г, то его увеличения стоимости как край сжимаются (отметьте, что край может быть меньше чем ноль). г выбран, чтобы отразить вероятность, что во время между последним обновлением государства ссылки и прибытием резервирования, ссылка стала слишком занятой, чтобы обработать резервирование. Определенно, для краев г или больше, вероятность создания плохого выбора маршрута, основанного на информации государства устаревшей ссылки, свернута.

От рис. 1 мы видим, что, когда край является большим (загрузка света), тогда стоимость пропорциональна длине. Однако, когда край падает ниже порога (g), стоимость увеличивает quadratically как функцию края. Разумный выбор для г - маленькое кратное число средней пропускной способности резервирования (R). Большой г может привести к пессимистической метрике, которая может излишне оштрафовать ссылки, у которых есть достаточная способность, тогда как маленький г мог привести к плохим маршрутам из-за государства устаревшей ссылки. Параметр β определяет, как быстро стоимость растет как снижения края. Мы экспериментировали с различными значениями (β, g) и нашли, что квадратная функция (β = 2) и г = 4 × R предлагает лучшую работу [11].

Рис. 1. Объединенная метрика стоимости.

Чтобы определить разумный выбор для параметра масштабирования α, рассмотрите соответствующее приращение стоимости в ситуации, где край равен нолю. Отметьте, который во время начиная с последнего обновления государства ссылки, "истинный" край, возможно, или увеличил или уменьшил. Если мы предполагаем, что обе возможности одинаково вероятны, то добавленная стоимость, когда край - ноль, должна балансировать стоимость двух различных "неправильных" решений маршрутизации, которые возможны: (1) у ссылки фактически есть недостаточная пропускная способность; (2) у ссылки фактически есть достаточная способность. Стоимость (1) - то, что резервирование отклонено. Это может быть выражено как стоимость ресурсов, которые использовало бы резервирование, если бы это было принято и использовало минимальный маршрут длины. Если эта минимальная длина маршрута - D, то стоимость - д-р, который - стоимость (2) то, что дополнительная ссылка (путь) более высокой стоимости используется, тратя впустую сетевые ресурсы. Эта добавленная стоимость - αg^βR. Установка этого равняется ДОКТОРУ, и решающий для α дает α = D/g ^β. Чтобы избежать подразумеваемого требования, чтобы вычислить D и α для каждого резервирования, мы просто определяем α основанный на типичном значении D.

2.2. Параллельный алгоритм исследования (СТР)

В алгоритме LCC, направляя информацию распределен всюду по сети, чтобы облегчить маршрутизацию запросов резервирования. Один недостаток этого подхода состоит в том, что маршрутизаторы должны поддержать много информации, большая часть которой никогда не используется. Действительно, если никакое резервирование не консультируется со специфической частью маршрутизации информации прежде, чем следующее обновление заменит это, то та часть маршрутизации информации не удовлетворяла никакой цели, и усилие, потраченное, чтобы создать это, было потрачено впустую. Кроме того, эти схемы полагаются на государство ссылки, распределенное от соседей, которые могли быть несвежими. Маршрутизация использующий государство устаревшей ссылки может строго ухудшить работу [9]. Параллельное исследование (СТР) алгоритм проявляет различный подход. Вместо того, чтобы поддерживать много динамической информации маршрутизации, это посылает пакеты исследования через сеть, чтобы собрать информацию маршрутизации, поскольку это необходимо. Это означает, что никакая посторонняя информация маршрутизации не должна быть поддержана. Только та информация, которая относится к выбору путей для фактического резервирования потока, запрошена.

Алгоритм СТР использует предвычисленный набор путей для каждой пары исходного адресата. Пакеты исследования посылают параллельно на всех этих путях адресату, и прерваны последним маршрутизатором перелета. Поскольку пакеты исследования проходят через сеть, каждый маршрутизатор на пути изменяет область в пакете, определяющем доступную пропускную способность на ее уходящей ссылке. Эта операция достаточно проста быть осуществленной в аппаратных средствах, позволяя исследования быть отправленной на проводной скорости. Отметьте, что сами промежуточные маршрутизаторы не хранят государства. Само исследование несет необходимую государственную информацию.

Когда пакеты исследования достигают последнего маршрутизатора перелета, это выбирает лучший путь для потока, основанного на полученной информации. Каждый пакет исследования включает область, указывающую, сколько исследований послали, разрешая последнему маршрутизатору перелета легко определить, когда он получил все исследования, в нормальном случае, где все исследования получены. Если одно или более исследований будут потеряны, то последний маршрутизатор перелета продолжится после блокировки времени. Последний маршрутизатор перелета выбирает самый короткий путь, для которого пропускная способность узкого места по крайней мере равна пропускной способности резервирования, если есть один или более таких путей. Если нет такого пути, резервирование понижено. Шаг инициализации требует, чтобы маршруты были предвычислены между каждым источником и адресатом.

Предвычисление: Мы предвычисляем дополнительные пути между каждой парой исходного адресата, использующей простой алгоритм, обрисованный в общих чертах в рис. 2, используя примечание, определенное в Таблице 2. Первоначально, мы находим самый короткий путь (использующий длину ссылки или счет перелета) между данной парой маршрутизаторов в сети и используем это как базовую метрику. Мы тогда берем каждый промежуточный узел и проверяем, ли длина пути через промежуточный узел в пределах некоторых связанных базового пути и отлична от базового пути. Если так, мы добавляем этот путь к набору дополнительных путей. Мы также ограничиваем число дополнительных путей, чтобы свернуть число исследований, которые посылают.

Рис. 2. Предвычисление дополнительных путей.

Таблица 2.
Примечание для алгоритма СТР

Примечание Объяснение

SPF (u, v) Самый короткий путь от u до v

P [x-y-z] Путь от x до z с промежуточным узлом y

Набор дополнительных путей от u до v сохранен в u

K_p Число дополнительных путей

L (u, v) Самая короткая длина пути от u до v

θ Мультипликативный фактор, ограничивающий длину пути

Примечание	Объяснение
SPF (u, v)	Самый короткий путь от u до v
P [x-y-z]	Путь от x до z с промежуточным узлом y
	Набор дополнительных путей от u до v сохранен в u
K_p	Число дополнительных путей
L (u, v)	Самая короткая длина пути от u до v
θ	Мультипликативный фактор, ограничивающий длину пути

Нужно также отметить что: (1) предвычисление сделано только, когда есть существенные изменения в государстве ссылки; (2) по требованию маршруты вычислены, используя статическую информацию (длины пути) о сетевой топологии, которая делает маршруты относительно здравыми к колебаниям в качестве пути. Мы комментируем больше воздействие использования статических метрик предвычисления на качестве путей в Разделе 5.3.

2.3. Результаты для внутридомена маршрутизация QoS

Мы теперь представляем результаты моделирования для LCC и СТР, направляющих протоколы для контекста внутридомена. Сетевая конфигурация для этого исследования моделирования была выбрана, чтобы быть представительной для очень широкой сети области. У этой сети есть узлы в каждой из 20 наибольших столичных областей в Соединенных Штатах (см. рис. 3), и уменьшенная триангуляция Delaunay. Преимущество триангуляции Delaunay состоит в том, что это позволяет ограниченное число дополнительных путей между данным источником и адресатом, значительно не увеличивая стоимость полной сети. Полная топология напоминает основную топологию опорной сети NSFNET. Возникновение трафика и завершение в каждом узле были выбраны, чтобы быть пропорциональными населению области метро, поданной узлом, и трафик между узлами был также выбран, основан на поселениях этих двух узлов. Это приводит к виду неравного распределения трафика, которое типично для реальных сетей. Ссылки в сети также проставлены размеры, чтобы дать возможность им нести ожидаемый трафик. Определение размеров ссылок, чтобы иметь соответствующую способность важно для реалистического исследования маршрутизации, так как ужасно спроектированная сеть может легко исказить результаты, приводя к несоответствующим заключениям об относительных достоинствах различных алгоритмов маршрутизации. Отметьте, что мы не используем случайный генератор топологии с произвольными ссылками, так как результаты для такой топологии являются трудными сделать вывод.

Рис. 3. Национальная сетевая топология.

Статистика ссылки: мощности ссылки были выбраны, используя основанную на ограничении сетевую методологию дизайна, развитую в [12]. Метод выбирает мощности ссылки, которые достаточны, чтобы нести любую конфигурацию трафика, которая удовлетворяет определенные ограничения трафика. Основанный на ограничении метод дизайна берет топологию и набор ограничений трафика и использует линейное программирование, чтобы найти ряд мощностей ссылки достаточным, чтобы обработать все условия трафика, удовлетворяющие ограничения трафика, предполагая, что трафик направлен, используя самые короткие пути. Этот процесс приводит к широкому диапазону мощностей ссылки, с наибольшей полной ссылкой, являющейся 32 разами такого размера, как наименьшее.

Отметьте, что для остальной части этого обсуждения, фактическое значение способности ссылки является несоответствующим, так как значения резервирования выражены как фракция способности ссылки и не как абсолютное значение, делающее наши моделирования, настолько общие насколько возможно. Наименьшая ссылка - ссылка между Сиэтлом и Денвером. Определенно, двунаправленные ссылки между Атлантой и Питсбургом (2.53 раза), Хьюстон и Майами (2.84 раза), Сиэтл и Сан-Франциско (способность 3.75 времен Сиэтла и Денвера), Сиэтла и Миннесоты (6.14 раз) и С-Louis и Атланта (6.32 раз) и могут быть тематическими категориями, поскольку потенциальное узкое место связывается, другие мощности ссылки - по крайней мере порядок величины больше чем Сиэтл-денверская ссылка. У запросов, которые пересекают вышеупомянутые ссылки узкого места, будет более высокая вероятность того, чтобы быть отклоненным. Мы подчеркиваем, что мы не используем искусственную топологию с изобретенными узкими местами. Скорее мы используем фактические поселения городов и получаем реалистическую модель трафика, которая является представительной для ожидаемого трафика между городами. Кроме того, любая топология, у которой есть высокая пропорция ссылок узкого места, нереалистична, так как у типичной топологии ISP есть ссылки большой емкости с первичными узкими местами, появляющимися как доступ и всматривающиеся ссылки [6].

В моделированиях запросы резервирования достигают каждого узла, в нормах, которые пропорциональны населению области, поданной узлом. Межвремя прибытия и времена занятости резервирования по экспоненте распределены. Отметьте, что мы НЕ моделируем прибытие пакетов, но прибытие запросов резервирования. Адресат каждого резервирования выбран беспорядочно, но с выбором, нагруженным относительным популяционным размером возможных адресатов.

Есть несколько числовых параметров, которые различны по моделированиям. У каждого параметра есть значение значения по умолчанию. Всякий раз, когда один параметр различен по данной диаграмме, другим параметрам назначают их значения значения по умолчанию. Каждый сеанс в нашем моделировании является представительным для совокупного резервирования или макропотока, так как маловероятно, что стоимость/накладные расходы ориентируемой на резервирование модели выполнима для микропотоков или индивидуального резервирования. Кроме того, мы предполагаем, что у сеансов есть равный приоритет, и что ISP развертывает свой доход, неся так много сеансов насколько возможно.

Системное вычисление загрузки: Предположите, что скупой размер резервирования, выраженный как фракция способности ссылки, является b, тогда n = 1/b - число одновременных сеансов, которые могут занять ссылку. У каждого подключения есть по экспоненте распределенная продолжительность запроса μ = 1/MHT. Это соответствует сервисной норме n μ. Если запросы достигают скупой нормы прибытия λ, то предлагаемой загрузкой дают . Отметьте, что предлагаемая загрузка может быть больше чем 1, так как это просто соответствует запросам, достигающим нормы, которая превышает норму, по которой запросы заканчивают (конец времени занятости запроса). Таким образом, предлагаемая загрузка 1.2, просто подразумевает, что 16.67 % в среднем будут автоматически отклонены по прибытию, так как не будет достаточно многих ресурсов.

Параметры настройки параметра протокола: значение значения по умолчанию скупого времени занятости (MHT), который является 60 раз модулями. В диаграммах фракция ссылки - отношение пропускной способности резервирования к пропускной способности наименьшей полной ссылки в сети (значение значения по умолчанию фракции ссылки.05 или 5 % наименьшей ссылки). Период обновления значения по умолчанию (время между государственными обновлениями) является 30 модулями для LCC. Число значения по умолчанию дополнительных путей, на которых исследованиях СТР 6.

Метрики работы: первичная метрика - Фракция Отклонения (фракция отклоненных запросов), который обратно пропорционально пропорционален доходу ISP. Мы также определяем порог для данной маршрутизации алгоритма, чтобы быть предлагаемой загрузкой, при которой фракция отклонения равняется.001. так как они - anecdotally типичные операционные уровни для ISPs.

Маршрутизация алгоритмов: Кроме LCC и СТР, результаты также включают (1) МИЛЛИГЕНРИ, минимальный алгоритм счета перелета, который вычисляет самый короткий путь, используя алгоритм Dijkstra’s со счетом перелета как метрика;, (2) СОКРАЩАЮТ, вариант МИЛЛИГЕНРИ, который сначала удаляет ссылки, которые испытывают недостаток в пропускной способности, чтобы нести резервирование, и затем вычисляют самый короткий путь, используя счет перелета; (3) WSP, само-самый короткий алгоритм пути [13] и [14], который поддерживает ряд дополнительных путей между каждым источником и адресатом, размещенным в увеличивающемся заказе счета перелета. Когда запрос прибывает, путь с наибольшей пропускной способностью узкого места выбран от набора путей с самым коротким счетом перелета.

Блокирование вероятности: рис. 4 сравнивает вероятность блокирования, наблюдаемую для нескольких различных алгоритмов маршрутизации, включая алгоритмы СТР и LCC. Показы результата, что LCC и алгоритмы СТР значительно выигрывают у других алгоритмов, с LCC выполнение немного лучше чем Стр ⁴ МИЛЛИГЕНРИ и СОКРАЩАЮТ алгоритмы, выступают намного хуже чем другие алгоритмы, показывая этому, маршрутизация QoS может обеспечить существенно лучшую работу чем обычные методы. традиционная маршрутизация. Дополнительные результаты для этих алгоритмов могут быть найдены в Касательно [11].

Рис. 4. Фракция отклонения QoS маршрутизация протоколов.

Показав льготам версий внутридомена LCC и СТР, мы теперь продолжим расширять их, чтобы поддержать маршрутизацию через домены. Мы отмечаем, что прежде всего из-за причин частной жизни ISP, не возможно непосредственно использовать версии внутридомена в окружающей среде междомена. В следующих разделах мы опишем версии междомена LCC и СТР и оценим их экстенсивно на реалистической топологии междомена.

3. Междомен QoS маршрутизация алгоритмов

Цель предложенного междомена, направляющего алгоритм, состоит в том, чтобы выбрать свободный исходный маршрут, присоединяясь к конечным точкам потока. Начиная со всматривающихся ссылок часто пункты скопления для сетевого трафика, осторожный выбор всматривающихся ссылок может оказать существенное влияние на вероятность успеха. Поскольку выбор маршрута междомена должен быть сделан без выгоды детализированного знания внутренней конфигурации каждого домена, это необходимо, чтобы оценить ресурсы количества или стоимость, понесенную потоком, когда это пересекает домен. В этом разделе мы расширяем и LCC и СТР, исследуют алгоритмы и описывают средства оценить стоимость внутридомена, выполняя QoS, направляющий через домены. Мы начинаем с описания простой оверлейной архитектуры сети, которая допустила бы QoS маршрутизация механизмов, представленных в этой газете.

3.1. Оверлейная архитектура узла

Ключевой компонент, чтобы допустить этому виду маршрутизации QoS является оверлейной архитектурой узла, чтобы выполнить специализированное всматривающееся распространение государства ссылки так же как источник, направляющий, который важен по отношению к механизмам маршрутизации, представленным в этой газете. По существу, так как ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ не может использоваться, чтобы распространить всматривающееся государство ссылки, которое является основным для нашего QoS маршрутизация механизмов, мы принимаем использование оверлейной сети, посредством чего оверлейные узлы исследовали бы другие оверлейные узлы, чтобы получить всматривающееся государство ссылки. Это требует, чтобы осторожное размещение оверлейных узлов приблизило всматривающуюся информацию ссылки. По существу, государство физической всматривающейся ссылки (доступная пропускная способность) передано к оверлейному узлу в том домене. Этот оверлейный узел тогда передает всматривающуюся информацию ссылки другим оверлейным узлам в других доменах.

Для оверлейного узла также возможно исследовать доступную пропускную способность всматривающейся ссылки, используя базируемые методики томографии [15], [16] и [17]. Эти методики основаны на паре пакета или исследовании поезда пакета, где взрывы одинаково раздельных пакетов однородного размера введены в путь интереса, и доступная информация пропускной способности выведена основанная на отношениях между входным промежутком межпакета и наблюдаемыми промежутками в выводе.

Пока, мы предполагаем, что КАК предоставляет всматривающуюся информацию ссылки к оверлейному узлу. Мы исследуем значения более подробно в Разделе 6.

Рис. 5 показывает иерархии с двумя уровнями, которую мы усиливаем, чтобы распространить равноправный информационный обмен государства ссылки также, так же как для того, чтобы направить пакеты потока. Как может быть замечен по числу, оверлейный узел может выбрать специфическую всматривающуюся ссылку выбором оверлейные узлы, приложенные к соответствующим основным всматривающимся узлам. Для фактической маршрутизации потока все пакеты переданы к оверлейному узлу в местном домене, который тогда использует виртуальную оверлейную топологию, чтобы выбрать исходный маршрут доменов, включая всматривающийся определенный для ссылки путь. Это достигнуто, выбирая промежуточные оверлейные узлы, которые "смежны" с отобранными всматривающимися ссылками. "Смежность" используется, чтобы гарантировать, что выбирание специфической оверлейной пары узла в различных доменах вынудило бы весь трафик пойти через специфическую всматривающуюся ссылку между теми доменами.

Рис. 5. Наложите сетевую архитектуру для маршрутизации QoS.

Важно отметить, что предложенная архитектура не полагается на ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ, чтобы выполнить маршрутизацию. Что еще более важно оверлейный узел может гибко исследовать для любой метрики QoS, включая время ожидания, колебание, и т.д. Мы обсуждаем оверлейную архитектуру более подробно в Разделе 6. Для остальной части обсуждения мы предполагаем, что оверлейные узлы выполняют всматривающееся распространение государства ссылки наряду с фактическим отправлением пакетов, принадлежащих потоку вдоль исходного маршрута, выбранного, выполняя алгоритмы QoS, представленные в этой газете в оверлейных узлах. Кроме того, мы будем использовать равноправный информационный обмен узлов, чтобы обратиться к всматривающимся "оверлейным" узлам, описывая алгоритмы.

3.2. Междомен Наименее Объединенная Маршрутизация Стоимости

Междомен алгоритм LCC включает две части. Одна часть распределяет информацию о всматривающихся ссылках те домены соединения. Всматривающаяся информация ссылки включает свойственные затраты всматривающихся ссылок (характеризованный здесь физической длиной ссылок) и их полезная мощность. Всматривающаяся информация ссылки может быть соединена, чтобы улучшить масшабируемость, но мы не обращаемся к проблеме скопления здесь. Недавние работы [18] и [19] упоминают трафик, технические расширения, предложенные для OSPF, могут быть расширены на ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ. В нашем случае это достаточно, если оверлейный маршрутизатор рекламирует признак пропускной способности узкого места на пути к оверлейному узлу другого домена. Эта информация достаточна в определении качества пути. По существу маршрутизатор сравнил бы признак, рекламируемый его соседом с пропускной способностью на его собственной всматривающейся ссылке тому соседу и устанавливать признак пути в ниже двух.

Это должно быть повторено, что только всматривающаяся информация узла обменена через домены. Если есть большое количество всматривающихся узлов, небольшое количество оверлейных узлов, которые смежны со всматривающимися узлами, может определяться, чтобы вести себя в манере, подобной динамикам ПОГРАНИЧНОГО МЕЖСЕТЕВОГО ПРОТОКОЛА. Вторая часть междомена алгоритм LCC принимает решения маршрутизации в поток. Концептуально это сделано, вычисляя наименее путь стоимости между конечными точками.

Стоимость пути определена, чтобы быть стоимостью всматривающихся ссылок на пути (вычисленное использование объединенной метрики стоимости, введенной в предыдущем разделе), плюс предполагаемая стоимость сегментов в пределах каждого домена на пути. Мы теперь описываем манеру, в которой оценены затраты сегмента внутридомена.

• Географическая оценка (GEO): географический метод оценки использует географическую длину сегмента пути в пределах домена, как предполагаемая стоимость. Это подразумевает, что распределенная государственная информация включает географические координаты маршрутизаторов в концах всматривающихся ссылок. Поскольку эта информация является статической, она не должна часто обновляться. Мы отмечаем, что есть различие между географической длиной пути между двумя узлами, и фактической физической длиной пути, которая состоит из реальных ссылок между двумя узлами. Выгода этого подхода - то, что он не нуждается ни в какой дополнительной информации государства ссылки, и может быть легко развернут, так как используемая информация является статической и не составляющей собственность.
• Статическая Оценка Пути (ИСПАНИЯ Г): алгоритм ИСПАНИИ Г принимает более точную статическую информацию в процессе выбора маршрута. Определенно, эта схема предполагает, что маршруты внутридомена вычислены, используя реальные физические длины пути, в противоположность использованию географических приближений. Этот подход уверен в статических длинах пути между парами узла входа/выхода доменов, которые могут измениться в очень длинных временных рамках, позволяющих нечастые обновления государства ссылки на длинах пути.
• Соединяющаяся Информация Пути: информация длины пути может быть соединена и передана маршрутизаторами края к другим доменам. Предположите, что есть x равноправный информационный обмен маршрутизаторов в специфическом домене. Таким образом, есть O (x²) пути, который должен быть вычислен, чтобы найти длину пути. Однако, можно выбрать, вершина k максимально отделяют пути и составляют в среднем информацию счета перелета, которая будет передана к другим доменам. Выбор вершины k пути был бы основан на доступной способности ссылки ссылки узкого места на каждом из путей. С изменениями в сетевой топологии это только необходимо, чтобы повторно вычислить пути, если узкое место связывает изменение. Определенно, список ссылок узкого места может быть собран упорядоченный основанный на доступной способности ссылки. Только если ссылки с самой высокой полезной мощностью терпят неудачу, был бы, пути должны быть повторно вычислены и повторно усреднены. Иначе, алгоритм внутридомена продолжил бы использовать ссылки с большинством полезной мощности. Мы не рассматриваем длин пути (счет перелета) как секрет фирмы. Кроме того, разглашение этой информации приносит пользу и провайдеру и клиентам.
• оценка значения True (TRU): оценка значения True не так практический метод оценки, как это - точка отсчета для того, чтобы ограничить работу этого класса алгоритмов. В этом методе мы предполагаем, что стоимость пути в пределах каждого домена вычислена, предполагая, что всем ссылкам назначают вес, основанный на объединенной метрике стоимости (Eq. (1)). Эффективно, эта схема предполагает, что информация о физических длинах ссылки так же как доступной способности ссылки распространяла для всех ссылок через все домены. Объединенная метрика стоимости тогда используется, чтобы определить затраты пути в пределах каждого домена. Мы повторяем, что этот подход не предназначен, чтобы быть примененным практически, из-за явного тома и частоты информации, которая должна быть обменена.

Операция Алгоритма: рис. 6 показывает операции GEO и ИСПАНИИ Г. Источник создает виртуальный граф адресату, и назначает всматривающимся ссылкам вес, определенный объединенной метрикой стоимости. Например, ссылке от (ER_w, ER_x) назначают стоимость C [ER_w, ER_x], где C [u, v] как определен в Eq. (1). Для сегментов пути внутридомена мы предполагаем, что информация соединена и распространена как в механизме ИСПАНИИ Г. В случае GEO информация о координатах говорит входной маршрутизатор ER_x и маршрутизатор выхода ER_y, распространен, позволяя стоимость виртуальной ссылки между ними быть назначенным вес, определенный Евклидовом расстоянием между ними. Для ИСПАНИИ Г вес - совокупная длина физических ссылок на самом коротком пути между ними. Нужно отметить, что и эти веса являются статическими и не должны распределяться неоднократно. Для TRU объединенная метрика стоимости назначена для сегментов пути внутридомена также использование информации, обмененной через домены. Как только виртуальный граф создан, и веса назначены, самый короткий алгоритм пути Dijkstra’s выполнен, чтобы получить самый короткий путь из источника адресату на уровне междомена.

Рис. 6. Маршрутизация использующий LCC базировала алгоритмы.

Вышеупомянутое самое короткое вычисление пути только обеспечивает высокопоставленный путь, так как оно не принимает знание индивидуальных ссылок. Таким образом, когда высокопоставленный путь выбран, и резервирование начато, есть механизм второго уровня, чтобы вычислить фактические пути внутридомена. Например, запрос резервирования, происходящий в источнике в рис. 6, достигнет входного маршрутизатора ER_x, основанный на высокопоставленном пути, который отобран. В этом пункте входной маршрутизатор мог использовать вычисленное использование дерева самого короткого пути метрики стоимости LCC (для маршрутизации внутридомена), достигнуть маршрутизатора выхода, ER_y. Разъединение вычисления пути междомена и внутридомена позволяет, что любая метрика могла использоваться в этом случае согласно политике, базируемой, направляя.

Алгоритм TRU предполагает, что междомен алгоритм LCC объединен с использованием LCC на уровне внутридомена, также. Однако, мы повторяем, что TRU не практическая схема и исключительно предназначен, чтобы обеспечить, верхнее привязывало работу базируемых алгоритмов SPF. Кроме того, использование LCC на уровне междомена не требует использования LCC (или любой другой определенный алгоритм) на уровне внутридомена. Из-за ограничений политики, мы ожидаем, что это трудно, если не невозможный, чтобы наложить использование последовательной непрерывной метрики для выбора QoS ограничил путь.

3.3. Маршрутизация исследования параллели междомена

В этом разделе мы расширяем алгоритм СТР для междомена маршрутизация QoS. Как в контексте внутридомена, алгоритм СТР вовлекает передачу пакетов исследования от пункта происхождения потока вдоль нескольких предвычисленных путей междомена к пункту адресата для потока. Эти пути междомена - свободные исходные маршруты, определенные на оверлейном уровне сети, которые определяют домены, которые будут пересечены, и всматривающиеся ссылки имели обыкновение проходить между доменами (снова, это сделано косвенно, выбирая соответствующие оверлейные узлы, приложенные к выбранной всматривающейся ссылке). Поскольку исследования проводят путь, они собирают информацию состояния, которая используется маршрутизатором в конце адресата, определить лучший путь для потока, чтобы взять. Для остальной части этой бумаги мы предполагаем, что собранная информация состояния - пропускная способность узкого места на пути. Другие метрики, такие как длины очереди, время ожидания ссылки могло также быть измерено оверлейными узлами в зависимости от типа требуемого QoS.

Согласно нашей полной структуре, различные методы маршрутизации могут использоваться в пределах доменов. В этом разделе мы сосредотачиваемся на случае, где параллельное исследование используется на уровне внутридомена, так же как на уровне междомена. Однако, мы впоследствии описываем, как алгоритм может использоваться для маршрутизации междомена в комбинации с другим внутридоменом, направляющим механизмы. Чтобы описать этот объединенный алгоритм ясно, мы различаем макроисследования, которые используются для исследования междомена и микрозондов, которые используются в пределах доменов.

Шаг инициализации: первый шаг должен предвычислить дополнительные пути между всматривающимися узлами. Мы используем оверлейную сеть, описанную ранее, составленный из всматривающихся оверлейных узлов, которые говорят с друг другом. Как прежде, мы предполагаем, что доступная способность ссылки при всматривающихся ссылках распространена через домены. Кроме того, мы предполагаем, что физическая длина пути между входом и узлами выхода также известна через домены (подобный подходу ИСПАНИИ Г предыдущего раздела). Информация длины пути входа/выхода является статической. Однажды, у нас есть виртуальная топология всматривающихся узлов, мы используем подход предвычисления для параллельного алгоритма исследования в случае внутридомена. Эффективно, для каждой всматривающейся пары узла, мы выбираем промежуточный всматривающийся узел и создаем дополнительный путь. Маршруты вычислены, используя статическую информацию (длины пути) о сетевой топологии.

Теперь, ссылки в Интернете терпят неудачу наугад, и карты топологии были бы неправильными. Однако, мы ожидаем, что ссылки равноправного информационного обмена, которые типично важны по отношению к доходу провайдера, имели бы лучшую избыточность и потерпели бы неудачу - по базируемым механизмам чем случайные ссылки в Интернете. Мы ожидаем, что предвычисление часто не выполняется, так как состояние всматривающихся ссылок было бы относительно устойчиво по сравнению с другими ссылками. Снова, мы подчеркиваем, что предвычисление было бы восстановлено, только если ссылка фактически терпит неудачу вместо того, когда метрики ссылки (доступная пропускная способность) изменяются. Для большего количества обсуждения по масшабируемости механизма предвычисления, пожалуйста обратитесь к Разделу 6.

В объединенном алгоритме макроисследования начаты маршрутизатором в пункте происхождения потока, и проход макроисследований через Интернет вызывает передачу микрозондов в пределах каждого домена. Более точно, когда макроисследование достигает входного маршрутизатора для домена, входной маршрутизатор начинает несколько микрозондов, которые проходят через домен маршрутизатору выхода, определенному в пути междомена, содержавшемся в макроисследовании. Маршрутизатор выхода собирает информацию в микрозондах, выбирает лучший путь и затем вперед макроисследование вдоль пути междомена, после добавления к этому, информация, описывающая доступную пропускную способность на отобранном пути внутридомена.

Когда макроисследования обработаны в закончившемся маршрутизаторе для потока, это выбирает лучший путь и вперед пакет резервирования назад вдоль свободного исходного маршрута. Части внутридомена пути заполнены в индивидуальными доменами, основаны на ранее отобранном микрозонде. Это подразумевает конечно, что маршрутизатор выхода сохраняет эту информацию для короткого промежутка времени, так, чтобы это было доступно, если и когда пакет резервирования возвращается вдоль пути. Отметьте, что этот процесс поддерживает частную природу сегментов пути внутридомена. Единственное государство, сообщенное вне домена, является доступной пропускной способностью узкого места на выбранном пути. Информация, хранившая в маршрутизаторах, зависима от местоположения:

Внутренний маршрутизатор: маршрутизатор в пределах домена хранит дополнительные пути маршрутизаторам края в домене. Если есть относительно большое количество маршрутизаторов края, внутренний маршрутизатор может хранить единственный путь каждому маршрутизатору края.

Маршрутизатор края (логин): Мы назначаем маршрутизатор, который соединяется с другими всматривающимися маршрутизаторами в других доменах как логин или Промежуточный маршрутизатор Адресата. Логин хранит дополнительные пути к другому логину в пределах домена. Логин также хранит пути к другому логину в других доменах.

Мы показываем типовому запросу и исследованиям, произведенным этим в рис. 7. Мы проследим типовой непрерывный путь, поскольку это пересекает домены или автономные системы (КАК). Первоначально, микрозонды, посланные из источника, достигают всех логинов в пределах КАК (например, достигая [ID_w, ID_v]). Магазин логина путь, включенный пока в местном масштабе и только, рекламирует пропускную способность узкого места или связанные метрики стоимости к другим доменам, уважая ограничения частной жизни домена. Затем, макроисследования порождены к другим доменам (ID_w → ID_x членство в наборе, вариант AS₃). ID_x в свою очередь порождает микрозонды, чтобы достигнуть ID_y. ID_y хранит путь исследования победы в местном масштабе и затем порождает макроисследование к ID_z членство в наборе, вариант AS₄. ID_z получает макроисследования от двух различных доменов [AS₁, AS₃], и выбирает лучшую опцию, которая является исследованием от ID_v в нашем примере. Это порождает микрозонды, которые наконец достигают адресата. После короткого периода отобрано побеждающее непрерывное исследование, и резервирование начато на обратном пути (Dst → ID_z → ID_v → Src).

Рис. 7. Многопутевая маршрутизация, используя СТР.

4. Результаты для междомена маршрутизация QoS

В этом разделе мы сначала опишем дизайн топологии междомена, чтобы оценить работу междомена QoS маршрутизация алгоритмов. Мы тогда описываем обширные результаты на работе LCC и версий СТР наряду с расширениями, чтобы облегчить их развертывание.

4.1. Дизайн топологии междомена

В этом разделе мы описываем дизайн междомена, направляющего сеть, которая может использоваться, чтобы реалистично оценить работу QoS маршрутизация протоколов. Основание для сетевого дизайна подобно дизайну внутридомена, направляющего сеть, описанную в Разделе 2.3. Мы выбрали 30 столичных городов в Соединенных Штатах с наибольшими поселениями. Полная конфигурация сформирована, комбинируя восемь отдельных сетей, каждый охватывая подмножество городов. У двух из сетей есть национальные возможности, в то время как сохранение шести сетей ограничено региональными областями.

Есть два основных вида сетевых провайдеров в этой топологии: Национальный и Региональный ISP’s. Мы используем следующую эвристику, чтобы выбрать членов любого ISP:

Национальный ISP: город считают членом национального ISP с вероятностью p = 0.8.

Региональный ISP: Как только географическая область решена для регионального ISP, мы определяем местонахождение приблизительного центра области и находим 10 самых близких городов в порядке расстояния. Мы тогда выбираем эти города, чтобы быть участником с вероятностью p.

Мы используем распределение двух Национальных ISP’s, и шести Региональных ISP’s. Национальный ISP’s - полные графы и покрывает 80 % сети (25 узлов). Среди регионального ISP’s есть три лучшей звездной топологии (см. рис. 8), две триангуляции Delaunay и одна полная топология графа (см. рис. 9). Триангуляция Delaunay [20] топология позволяет параллельные пути между узлами, свертывая число таких параллельных путей, учитывающих рентабельную топологию. Единственный город может быть членом многократного ISP’s. Мы фиксируем это, создавая отдельный виртуальный узел для каждого домена, который включает город. В таких случаях всматривающиеся ссылки - установка между этими виртуальными узлами. Типы всматривающихся ссылок могут быть тематическими категориями как провайдером клиента (Маленький, ПОСКОЛЬКУ это платит большее ЧТО КАСАЕТСЯ доступа), и пэр-пэр (и ASes имеют сопоставимый размер и находят взаимно выгодным, чтобы перевезти транзитом трафик друг через друга). В нашей топологии, каждом из шести региональных ISP’s, поделившихся ссылка пэра-пэра всякий раз, когда город присутствовал в обеих топологии, и поделился ссылкой провайдера клиента с национальным ISP’s в каждом городском подарке в каждой региональной топологии. Кроме того, 2 национальных ISP’s, поделившиеся ссылка пэра-пэра в каждом из городов, которые присутствовали в обоих топология ISP. У всей топологии повсюду есть 100 узлов. За большее количество деталей относительно топологии мы отсылаем читателя к [11].

Рис. 8. Региональный ISP: Лучшая Звезда (a) Региональный ISP: Западное Побережье (b) Региональный ISP: Юго-восток (c) Региональный ISP: Северо-восток.

Рис. 9. Региональный ISP: Delaunay и Полный Граф (a) Региональный ISP 2: Запад (b) Региональный ISP 4: Середина на запад (c) Региональный ISP 3: Восток.

Это разнообразное соединение топологии позволяет результатам моделирования быть применимым к общей топологии в противоположность специфической топологии. Мы используем основанный на ограничении метод дизайна, подобный подходу для внутридомена, направляющего топологию. Так как трафик можно теперь или послать в пределах домена или через домены, мы отдельно проставляем размеры ссылок для intra и маршрутизации междомена, и берем сумму измерений для полной сети. В моделировании мы гарантируем, что трафик внутридомена ограничен, чтобы использовать ссылки в пределах домена, и не использование, всматривающееся ссылки.

Маршрутизация политики: Маршрутизация политики часто диктует, как пакеты направлены и в пределах и через домены. Для нашего обсуждения мы хотели показать лучшей работе случая междомена QoS маршрутизация протоколов без ограничений политики. Нужно отметить, что любая политика, принятая специфическим доменом, могла потенциально ограничить пути, доступные для того, чтобы направить между специфической парой исходного адресата. Однако, детали фактической политики являются часто конфиденциальными и вне возможностей этой бумаги, которая имеет дело с аспектами работы маршрутизации QoS.

Параметры протокола: Как прежде, запросы резервирования достигают каждого узла, в нормах, которые пропорциональны населению области, поданной узлом. Межвремя прибытия и времена занятости резервирования по экспоненте распределены. Используются однородные пропускные способности резервирования. Адресат каждого резервирования выбран беспорядочно, но с выбором, нагруженным относительным популяционным размером возможных адресатов. Трафик в этом случае распределен не только среди ряда узлов адресата, но также и среди ряда доменов адресата. Мощности ссылки меняются в зависимости от наименьшего существа 80 Mbps и наибольшего существа 15 Gbps. С таким большим различием мы используем требование пропускной способности сеанса значения по умолчанию 20 Mbps, а не неподвижной фракции ссылки. Скупое время занятости (MHT) также увеличено к 120 разам модули. Период обновления - 30 раз модули. Число значения по умолчанию дополнительных путей, на которых СТР посылает исследования, 6.

Назовите вероятность блокирования: рис. 10, рис. 11 и рис. 12 показывают работе QoS маршрутизация схем. Полные результаты фракции отклонения (рис. 10) показ, что СТР ясно превосходят TRU (фактор 2 усовершенствований в 10⁻³) и алгоритм GEO (фактор 8 усовершенствований в 10⁻³). Удивительно, что алгоритм СТР в состоянии выиграть у TRU несмотря на TRU вычисление самого короткого пути по требованию для каждого запроса. Алгоритм TRU все еще полагается на периодические обновления государства ссылки, и использование информации устаревшей ссылки может привести к неоптимальному выбору пути. Нужно также отметить, что с требуемой пропускной способностью (20 Mbps), который является почти 1/4-ым из наименьшей способности ссылки, легче насыщать ссылку, выбирая неминимальный путь. Алгоритм СТР также в состоянии выбрать дополнительные пути, у которых нет ссылок узкого места, вместе учитывая, лучше загружают распределение. Также возможно, что алгоритм TRU выбирает более длинные пути чем необходимый (никакая верхняя привязанная длина пути) увеличение шанса отказа резервирования так же как размещения дополнительной загрузки, которая могла затронуть другие подключения ⁵

Рис. 10. Фракция отклонения для междомена QoS маршрутизация протоколов.

Рис. 11. Фракция отклонения для междомена QoS (низкая пропускная способность узкого места).

Рис. 12. Фракция отклонения для междомена QoS (большая пропускная способность узкого места).

Алгоритм GEO значительно хуже и чем TRU и чем СТР. Выберите, что алгоритм GEO первое использование географические расстояния, чтобы выбрать равноправный информационный обмен узлов, и затем использует алгоритм LCC в пределах домена. Использование географических расстояний предполагает, что физические ссылки следуют за виртуальными географическими ссылками, который не имеет место.

Рис. 11 показывает этому, СТР обеспечивают существенную прибыль для путей с маленькими пропускными способностями узкого места ( "меньше чем или равняются", наклониться 150 Mbps), распределяя загрузку более эффективно и уменьшая вероятность насыщения этих путей. Для путей с большими пропускными способностями узкого места (между 600 Mbps и 2.4 Gbps), прибыль для СТР по другим схемам находится следовательно менее как показано в рис. 12, указывая, что комбинация государства устаревшей ссылки и маленьких ссылок может заставить традиционные самые короткие протоколы пути выступать плохо по сравнению с динамическим многопутевым протоколом как алгоритм СТР.

Эффект больших запросов пропускной способности: рис. 13 показывает воздействию увеличения пропускной способности запроса на пороге загрузки. Порог загрузки - максимальная загрузка, которая может быть поддержана во фракции отклонения 10⁻³. СТР как ожидаемые поддержки загрузка 0.48, TRU загрузка 0.2 и GEO загрузка 0.1 в значении значения по умолчанию 20 Mbps. Пороговые уменьшения загрузки как размер пропускной способности запроса увеличены.

Рис. 13. Изменение порога с размером пропускной способности запроса.

Деградация равноправного информационного обмена пропускной способности ссылки: рис. 14 составляет график отношения фракций отклонения GEO и алгоритмов TRU при загрузке 0.4, изменяя пропускную способность всматривающихся ссылок. В факторе деградации 0.5, разделена на два способность ссылки всех всматривающихся ссылок. Как более низкий фактор деградации, всматривающиеся ссылки насыщаются быстро, и выбор всматривающейся ссылки не столь важен. Это затрагивает непрерывный алгоритм TRU, который использует объединенную метрику стоимости (Eq. (1)) повсюду. Так как алгоритм GEO использует метрику стоимости только для всматривающихся ссылок, и всматривающиеся ссылки насыщаются в скором времени, работа и TRU и GEO будет приблизительно сходиться в низких факторах деградации. Таким образом, отношение их фракций отклонения ниже. Поскольку мы увеличиваем всматривающуюся пропускную способность ссылки, алгоритм TRU начинает выигрывать у GEO и отношения двух увеличений.

Рис. 14. Воздействие сокращения равноправного информационного обмена пропускной способности ссылки (междомен).

Воздействие периода обновления: рис. 15 показывает воздействию изменения периода обновления на пороге загрузки и для TRU и для GEO. Как ожидается, порог уменьшается с большими обновлениями из-за использования информации государства устаревшей ссылки механизмом выбора маршрута. И падение TRU и GEO существенным количеством как период обновления становится такого размера, как MHT. Отметьте, что алгоритм СТР использует динамическое исследование и не полагается на обновления государства ссылки.

Рис. 15. Изменение порога с периодом обновления (междомен).

Воздействие α, г на LCC: рис. 16 показывает точности параметра г в вычислении метрики стоимости (Eq. (1)) для алгоритма LCC. Выберите, что г - порог, который вызывает настройку метрики стоимости к стоимости ссылки. Поскольку мы можем видеть, наш выбор г для моделирований, которым показывает значение по умолчанию, вертикальная линия рядом оптимальна. Рис. 17 показывает эквивалентному сроку α, который является также близко к лучшему значению, которое может быть выбрано. Низкий срок α неблагоприятно затрагивает работу, так как эффект срока края в объединенной метрике стоимости должным образом не составляется.

Рис. 16. Изменение порога с г параметра LCC (междомен).

Рис. 17. Изменение порога с параметром LCC α (междомен).

4.2. Маршрутизация задержек и захват ресурса

Один недостаток СТР состоит в том, что, если два запроса, происходящие при различных исследованиях новичка узлов (говорят r₁ и r₂) и, совместно используют пути таким образом, что самый лучший путь для r₂ - подмножество самого лучшего пути P для r₁. Позвольте нам далее предполагать, что исследование для r₁ начато, прежде r₂, но r₂ начинает обратное резервирование прежде r₁. Наконец, адресат для r₂, как предполагается, является одним из промежуточных маршрутизаторов на P. Это может случиться, что обратное резервирование для r₁ могло потерпеть неудачу, поскольку ресурсы были "захвачены" r₂. Это может случиться, так как последний маршрутизатор перелета на P не сознает r₂. В то время как это просто обойти эту проблему, устанавливая своего рода мягкое государство в передовой проход исследования, мы сначала показываем той этой проблеме, не затрагивает работу СТР в нашей топологии междомена. Мы изменяем алгоритм СТР, чтобы включать задержки распространения исследований, поскольку они пересекают путь. Мы показываем алгоритму СТР для задержек исследования 3 и 5 модулей по сравнению с базовым алгоритмом СТР в рис. 18. Ясно, что задержки не воздействуют на работу алгоритма СТР.

Рис. 18. СТР с задержками распространения.

Однако, возможно, что вышеупомянутый сценарий может заставить обратное резервирование быть отклоненным. Наивное решение состоит в том, чтобы установить переходное государство запроса в передовой проход. Однако, это потенциально заблокировало бы ресурсы на всех параллельных путях, которые исследованы для того резервирования, приводя к серьезной потере использования. Вместо этого мы предлагаем альтернативу, которая требует некоторой разведки в маршрутизаторах. Определенно, мы предполагаем, что последний маршрутизатор перелета, который начинает обратное резервирование, сохраняет переходное государство о статистике (качество) путей исследованный для того запроса. Тогда, когда запросу отказывают в ресурсах на обратном пути, последний маршрутизатор перелета начинает вторичное резервирование на следующем лучшем пути. Предположение - то, что запрос может терпеть достаточно большое время установки запроса для этого возвращающегося механизма, чтобы найти альтернативный маршрут. Это не неблагоразумное предположение, данное, которые текут, резервирование для более длинных продолжительностей.

4.3. Масштабирование к большой топологии междомена

В этом разделе мы представляем результаты, описывающие случайную интернет-топологию, используя Технический GT-ITM Джорджии [21] генератор топологии. Мы привыкли иерархический метод Окурка транзита для этого, создает иерархию с 2 уровнями, с каждым высокопоставленным узлом, представляющим домен транзита, и со вторым уровнем, дающим каждый граф внутридомена. Затем, прикрепите домены окурка к каждому домену транзита. Наконец добавьте дополнительный окурок транзита и края окурка окурка.

Параметры: входные параметры для генератора были 10 доменами транзита, с 31 узлом в домен транзита, 31 окурком в узел транзита и 40 узлов в окурок. Отметьте, что число окурков 9610, и число узлов в окурок транзита не относится к делу. Чтобы принять подобную политику определения размеров как в наших 100 топологии узла, мы отобразили каждый 31 узел домена транзита и узлы окурка в 31 наибольший столичный город в США. Трафик, произведенный каждым узлом окурка, был тем же самым. Провайдер клиента, всматривающийся ссылка между узлом окурка и узлом транзита, был основан на населении города. Ссылка пэра-пэра между узлами транзита двух городов была снова основана на числе узлов окурка, приложенных к узлу транзита (аналогичный "населению" узла транзита). Ссылка пэра-пэра между двумя узлами окурка основана на населении города, который представляет узел окурка. Мы использовали время занятости запроса 600 раз, когда модули и каждый запрос требуют пропускной способности 1 % наименьшей способности ссылки.

В рис. 19 мы изучаем работу GEO, LCC и схем СТР в терминах полной фракции отклонения для большой топологии междомена. Мы видим, что работа СТР и алгоритмов LCC столь же существенна как в меньшей топологии. Мы впоследствии показываем тому каждому алгоритму маршрутизации, может быть осуществимо развернут, используя механизмы, описанные в Разделе 6, и также прокомментировать накладные расходы обработки.

Рис. 19. Масштабирование к большому КАК топология (9610 доменов).

5. Расширение алгоритмов маршрутизации

Мы теперь опишем расширения к вышеупомянутому QoS маршрутизация алгоритмов, которые исследуют обмен между сложностью/масшабируемостью алгоритма и работой. У нас есть СТР и алгоритмы GEO в двух экстремальных значениях. Алгоритм СТР показывает лучшей работе, но также и подвергается большому верхнему должно к исследованиям, посылаемым, так же как требуя, чтобы все домены использовали алгоритм последовательно для, предают земле и intra маршрутизация домена на непрерывном пути. Оба из вышеупомянутого не делают алгоритм масштабируемым к большим сетям с разнообразными автономными системами. Алгоритм GEO с другой стороны использует просто статическую информацию, которая может быть получена без любых ограничений частной жизни между доменами и проста развернуться. Однако, у этого есть значительно худшая работа чем СТР. Мы стремимся улучшить оба алгоритма по-разному.

5.1. Улучшение работы GEO

В этом разделе мы описываем расширения, которые улучшают работу алгоритма GEO, поддерживая его непринужденность развертывания. Наша первая модификация (ИСПАНИЯ Г) должна использовать реальные физические длины ссылки в противоположность использованию виртуальных географических длин ссылки для того, чтобы направить в пределах домена ⁶, В то время как эта информация - определенный домен, это является не обязательно составляющим собственность, так как другой домен не будет в состоянии извлечь выгоду информацией о длинах ссылки, не зная дополнительную информацию о ссылке, таких как способность ссылки. Таким образом, высокопоставленный механизм выбора маршрута использует объединенную метрику стоимости при всматривающихся ссылках и физические длины ссылки при всех других ссылках как веса ссылки и вычисляет самый короткий путь. Как прежде, intra маршрутизация домена выполнен, используя алгоритм LCC. Наша следующая модификация (СТР Г) должна использовать алгоритм СТР для intra маршрутизации домена, используя виртуальные географические длины ссылки для маршрутизации междомена.

Заключительный шаг должен объединить эти два варианта выше и создать гибридный протокол (G:PP + ИСПАНИЯ), который использует реальные физические длины ссылки, чтобы найти путь междомена всматривающихся узлов (основанным на ИСПАНИИ Г) и использует параллельный алгоритм исследования для intra маршрутизации домена (основанный на СТР Г).

От рис. 20 мы видим 30%-ое усовершенствование ИСПАНИИ Г по GEO. СТР Г приводят к большему усовершенствованию 40 % по алгоритму GEO. Самая большая прибыль получена для (G:PP + ИСПАНИЯ) как показано в рис. 20. Оригинальному GEO и предварительным вариантам (СТР Г, ИСПАНИЯ Г) также показывают наряду с алгоритмами СТР и TRU. Поскольку мы можем видеть, гибридный протокол (G:PP + ИСПАНИЯ) выступает почти так же как непрерывные алгоритмы TRU и предлагает фактор 5 усовершенствований по базовому алгоритму GEO. Эта версия достигает надлежащего равновесия между использованием статической информации, уверяющей непринужденность развертывания, и работой.

Рис. 20. Работа гибридной схемы GEO.

5.2. Масштабируемый параллельный алгоритм исследования

СТР и алгоритмы TRU отражают два экстремальных значения в маршрутизации междомена. Алгоритм TRU - источник, направляющий подход, который предполагает, что вся информация известна в источнике и вычисляет непрерывный маршрут по прибытию подключения. Алгоритм СТР посылает исследования на предвычисленных путях, чтобы найти самый лучший маршрут. Однако, алгоритм СТР принимает существование запасных маршрутов через предвычисление. Оба протокола применены в последовательной манере через все домены. ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ позволяет каждому домену использовать свой собственный механизм выбора маршрута, приводящий к в местном масштабе оптимальным сегментам, но глобально подоптимальным путям. Мы понимаем, что принуждение каждого домена использовать тот же самый протокол маршрутизации не практично в реальных сетях. Кроме того, в то время как СТР ясно выигрывают у других вариантов, есть все еще верхнее, связанное с передачей исследований особенно в пределах доменов из-за явного числа дополнительных путей, которые доступны.

Мы предлагаем гибридную версию СТР и алгоритмов LCC, обозначенных как PPLC, который более масштабируем чем оригинальный алгоритм СТР. Этот алгоритм использует подход макроисследования, чтобы найти высокопоставленный путь всматривающихся узлов как прежде. В то время как базовый алгоритм СТР использовал микро исследования для того, чтобы направить в пределах домена, мы удаляем то требование и позволяем домену использовать любой самый короткий механизм пути. Поскольку наши результаты для внутридомена, направляющего (рис. 4), показали, алгоритм LCC выполняет лучшее для того, чтобы направить в пределах домена. Следовательно, мы используем LCC для маршрутизации внутридомена и используем СТР для того, чтобы направить между доменами. Этот вариант позволяет домену использовать более простой внутридомен, направляющий механизм, и более масштабируем. Акцент в последующих диаграммах должен видеть, что промежуток работы сужается между вариантом PPLC и оригинальным алгоритмом СТР. Период обновления государства ссылки - один дополнительный параметр PPLC, который перенесен от компонента LCC. Периодичность маршрутизации обновлений решает точность алгоритма LCC для маршрутизации внутридомена.

Рис. 21 показывает работе варианта PPLC в различных периодах обновления наряду с работой индивидуальных СТР и алгоритмов TRU, где PPLC (x) является PPLC с периодом обновления x. Есть существенное повышение работы PPLC (30) по TRU почти с 65%-ым усовершенствованием во фракции отклонения 10⁻³. PPLC (15) получает фактор 2 усовершенствований по TRU, и у базового алгоритма СТР только есть 17%-ое усовершенствование по этому. Таким образом, мы видим, что этот гибридный вариант не только значительно уменьшил наверху по сравнению с обоими СТР и TRU но также и обеспечивает равновесие между СТР и алгоритмами TRU в сложности работы так же как обработки.

Рис. 21. Работа PPLC по сравнению с СТР и алгоритмами TRU.

5.3. Усовершенствованное предвычисление для параллельного исследования

Интересно, алгоритм LCC незначительно лучше чем алгоритм СТР в топологии ISP для внутридомена, направляющего (рис. 4), тогда как СТР ясно превосходят LCC в сценарии междомена от рис. 10. Это происходит прежде всего из-за накладывающихся путей, которые выбраны статическим алгоритмом предвычисления, описанным в рис. 2. Если пути накладываются, особенно при ссылках узкого места, это отрицает льготы исследования многократных путей, так как большинство путей должно будет все еще пройти то же самое узкое место. Нехватка отличных путей, собранных алгоритмом предвычисления СТР, позволяет LCC выступать лучше чем СТР.

Рис. 22 показывает различным дополнительным путям, доступным в установке внутридомена с выбором 1 являющийся значением по умолчанию самый короткий путь. Как ожидается, большинство запросов выбирает эту опцию, и другие альтернативы делятся ссылками с этим путем, устраняющим их от того, чтобы быть выбранным часто.

Рис. 22. Распределение запроса по индивидуальным путям (внутридомен).

Рис. 23 (a) и (b) показывает определенным примерам ограниченного разнообразия в выборах пути для двух пар исходного адресата в топологии внутридомена. Значения в круглых скобках рядом со ссылкой показывают путям, которые делятся той ссылкой. Как прежде, выбор пути (1) является значением по умолчанию самый короткий путь между узлами. У других ссылок только есть один путь, используя их. Например, в рис. 23 (a), для путей между Сан-Диего и Далласом, 5 из 6 путей используют ссылку от Сан-Диего до Лос-Анджелеса и ссылку от С-Louis до Далласа. В рис. 23 (b), для путей между Далласом и Хьюстоном, большинство ссылок принадлежит по крайней мере 3 путям.

Рис. 23. Путь, совместно использующий примеры (a) совместное использование пути между Сан-Диего и Далласом (b) совместное использование пути между Далласом и Хьюстоном.

Сценарий междомена с более разнообразной топологией как замечено в рис. 24 предлагает выборы пути, которые более отличны с меньшим количеством совместного использования ссылок, учитывающих более даже распределение запросов.

Рис. 24. Распределение запроса по индивидуальным путям (междомен).

Мы количественно фиксируем ссылки, которыми делятся между k путями для параллельного алгоритма исследования, используя следующую метрику, обозначенную как Путь, совместно использующий отношение (PSR), который является отношением (число ссылок в пути i) к (счет перелета пути i). Отношение 1 идеально, так как оно подразумевает, что у всех путей есть отличные ссылки и между путями нет никакого совместного использования. Мы получаем путь, совместно использующий отношение 0.82 для топологии междомена и 0.47 для национальной сети (внутридомен), ясно указывающий, что совместное использование ссылок находится значительно больше в национальной сети, ограничивая выбор пути алгоритма СТР. Мы выполнили дополнительные эксперименты на другой топологии внутридомена, которая обеспечивает более отличные дополнительные пути, включая топологию торуса [11]. Наши результаты подтверждают вышеупомянутое наблюдение, что с разумным разнообразием пути СТР всегда выигрывают у LCC. Нужно также отметить, что выборы, сделанные резервированием, также зависят от способности узкого места путей. Если у ссылок, которыми делятся между путями, будет достаточная способность, то это не будет оказывать так много влияния на работу в противоположность путям, которые делятся ссылками узкого места.

Однако, при условии, что разнообразие пути не данное предположение в обобщенной сети, мы увеличиваем алгоритм предвычисления для СТР, чтобы свернуть путь, совместно использующий, который испытан между предвычисленными дополнительными путями.

Усовершенствованный алгоритм предвычисления: Выберите, что оригинальный алгоритм предвычисления (от рис. 2) выбрал промежуточный узел i для данной пары исходного адресата (s, d), и проверил, отличался ли дополнительный путь от s → я → d от пути значения по умолчанию от s → d по крайней мере ссылкой и имел длину, сопоставимую пути значения по умолчанию. Мы увеличиваем алгоритм следующим образом. Позвольте S_{s, d} быть набором путей, которые были предвычислены пока для пары (s, d). Тогда, мы проверяем число лития ссылок, которые появляются и в потенциальном пути через меня, и в каждом пути в наборе S_{s, d}. Если длина потенциального пути привет, мы вычисляем отношение . Это отношение - эффективно 1 − PSR определенный ранее. Цель состоит в том, чтобы свернуть срок PS_i так, чтобы очень немного ссылок от нового пути наложились с существующими путями. Мы тогда вводим параметр моделирования, названный Путем, Связанным (СВИНЕЦ). Алгоритм проверяет, что "меньше чем или равняются", наклониться СВИНЕЦ PS_i , и включает путь в набор S_{s, d}, если проверка преуспевает, проводя в жизнь, что фактическое перекрытие между дополнительными путями ограничено сроком СВИНЦА.

Рис. 25 показывает льготам нового алгоритма предвычисления для параллельного исследования. Легенды показывают оригинальным СТР и алгоритмам LCC так же как двум новым линиям, где СТР (x) указывают, что Связанный Путь является x (например, СТР (0.8) указывает, что было самое большее 80%-ое перекрытие между дополнительными путями для каждой пары исходного адресата). СТР (0.8) представляют лучшую работу для параллельного исследования, выигрывая даже у алгоритма LCC. СТР (0.5) фактически делают хуже чем базовый алгоритм СТР, который не был ограничен. По существу, как уменьшения срока СВИНЦА, мы ограничиваем выбор дополнительных путей. Это не только ограничивает фактическое число отличных дополнительных путей между источником и адресатом, но также и вынуждает алгоритм выбрать потенциально более длинные пути, это неблагоприятно затрагивает работу.

Рис. 25. Расширение алгоритма предвычисления.

5.4. Резюме междомена QoS маршрутизация алгоритмов

Эти три схемы (СТР, TRU, GEO) представляют протоколы, которые прежде всего отличаются по природе маршрутизации обмененной информации. Алгоритм GEO использует статическую информацию о географическом расстоянии и является самым легким протоколом, чтобы развернуться этих трех схем, требующих незначительных модификаций к OSPF. У алгоритма TRU есть превосходящая работа для внутридомена, направляющего определенно из-за его способности дать компенсацию за государство устаревшей ссылки, принимая маршрутизацию решений. Однако, переутомление ссылки заявляют увеличения, когда длины пути увеличиваются (для маршрутизации междомена) и задержка размножения государства ссылки ко всем увеличениям узлов.

В результате алгоритм СТР появляется как лучший междомен, направляющий алгоритм по сравнению с другими схемами. Этот алгоритм использует современную информацию в механизме выбора пути, используя информацию, собранную исследованиями. Это было также приспособлено к набору изолированная природа каждого домена, посредством чего исследования только несут равноправный информационный обмен информации между доменами, в то время как другая информация домена остается строго частной к домену.

6. Выполнение маршрутизации алгоритмов

Есть несколько предположений, сделанных алгоритмами маршрутизации, представленными в этой газете, которая обычно не понималась бы в текущих сетях. Некоторые из механизмов, которые были бы барьерами, обсуждаются ниже.

6.1. Комментарии к масшабируемости, выполнимости и безопасности

• Равноправный информационный обмен ссылки заявляют распространение: алгоритмы, предложенные в этой газете, полагаются на распространение всматривающегося государства ссылки через провайдеров., Типично всматривающиеся договоренности ссылки - установка между провайдерами, основанными по соглашениям о сервисном обслуживании. Вопрос возникает относительно того, почему эта информация должна быть выпущена через различных провайдеров. Первичное побуждение для провайдеров, чтобы поделиться этой информацией: (a), чтобы предотвратить подоптимальную маршрутизацию и улучшить QoS для пользователей, переводя к увеличенному доходу провайдера; (b), чтобы использовать запасные маршруты кроме значения по умолчанию самый короткий путь или злободневная политическая проблема, направляющая механизмы, чтобы свернуть вероятность скопления.
В пределах единственного домена все маршрутизаторы рассматривают как равные, и внутридомен, направляющий протокол, объявляет обо всех известных путях всем маршрутизаторам. Напротив, в глобальном Интернете все ASes не равны, и КАК будет редко соглашаться оказать услугу транзита для всего ее связанного ASes ко всем адресатам. Поэтому, ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ позволяет маршрутизатору быть отборным в рекламных объявлениях маршрута, которые он посылает соседним маршрутизаторам. Это также непосредственно зависит по всматривающемуся соглашению между двумя доменами. Наше предложение к существующему всматривающемуся соглашению должно увеличить это с дополнительным условием, чтобы обработать дополнительный трафик, который может быть решен между провайдерами. Этот дополнительный трафик переводит к увеличенному доходу к транзиту, ПОСКОЛЬКУ это несло бы это. Единственное требование конечно, должен передать равноправный информационный обмен государства ссылки другим несоседним провайдерам. Мы полагаем, что обещание увеличенного дохода заставило бы любого провайдера распространять равноправный информационный обмен государства ссылки через многократных провайдеров, особенно когда есть ясные денежно-кредитные стимулы для того, чтобы делать так.
В терминах фактических механизмов, чтобы распространить равноправный информационный обмен государства ссылки, один такой подход должен использовать оверлейные сети, такие как РОН [22] и СПИННЫЕ ХРЕБТЫ [23]. Ключевая идея состоит в том, чтобы установить оверлейные узлы в границах провайдеров, которые исследуют друг друга. Это могло потребовать сотрудничества провайдера, но может также быть делегировано к оверлейному провайдеру третьего лица. Оверлейный провайдер начал бы исследование других всматривающихся оверлейных узлов и получил бы статистику, такую как доступная пропускная способность ссылки, или задержка.
Теперь, авторы РОНА упоминают, что их схема исследования, которая требует исследования любого оверлейного узла, не масштабировала бы хорошо в реальном включении окружающей среды тысяч ASes. Чтобы масштабировать хорошо, схема могла использовать базируемые механизмы различного порога, которые исследуют только, когда есть существенные изменения в сетевых метриках. Другая помощь масштабируемой архитектуре состоит в том, чтобы распространить исследованное государство в иерархической манере, подобной структурированному одноранговому оверлею [24]. Комбинация структурированного иерархического оверлея для масштабируемого исследования наряду с гибкостью информации обменяла между оверлейными результатами узлов в полной архитектуре, которая масштабировала бы хорошо.
• проблемы Безопасности: Одна из главных особенностей оверлейной сети - гибкость и настройка, предоставленная оверлейными узлами. В частности мы можем провести в жизнь несколько политики безопасности для расширения и защиты QoS маршрутизация алгоритмов от злонамеренных нападений. Определенно есть следующие механизмы, которые мы желаем использовать: – Заверенные всматривающиеся обновления ссылки: Оверлейные узлы обменивают обновления государства ссылки, используя идентификацию. Свидетельство базировалось, механизм может использоваться, посредством чего каждый оверлейный узел подписывает обновление государства ссылки с его свидетельством, чтобы проверить подлинность обновления. Это только необходимо для того, чтобы всмотреться оверлейные узлы, чтобы "доверять" друг другу. Таким образом, вместо того, чтобы требовать глобальной общественной ключевой инфраструктуры, которая непрактична, мы предлагаем, чтобы переходные трастовые отношения использовались, посредством чего возможности свидетельства только между двумя провайдерами. – Дополнительное кодирование: Кроме того, механизмы, такие как IPsec [25] туннелирование может быть установлено между оверлейными узлами, который обеспечивает обе конфиденциальности (ОСОБЕННО кодирование) и защита идентификации/целостности к пакетам IP. Это препятствует тому, чтобы злонамеренные нападавшие изменили обновления, чтобы искусственно увеличить или уменьшить важность пути, или даже переадресовать пакеты (нападение черной дыры), чтобы быть пониженным впоследствии. Кроме того, кодирование предотвращает подслушивание и разрешение нападавшему получить изображение сетевой топологии.

6.2. Осуществление параллельного исследования

• Сохранение частной жизни домена: Мы предполагаем, что маршрутизаторы края AS_i поддерживают две отдельных таблицы. Первая таблица - нормальная таблица маршрутизации, отражающая маршруты в пределах домена, и представляет информацию, частную к AS_i. Вторая таблица - таблица отображения с каждым входом, являющимся с 4 кортежами <клин, PEER_in, PEER_out, путь>, где PEER_in, PEER_out определяют вход и выход, всматривающийся узлы, принадлежащие AS_i, которые являются частью пути междомена для потока, идентифицированного клином. Область пути - выбранный путь в пределах домена.
В передовом проходе параллельного исследования маршрутизатор края PEER_in посылает микрозонды на дополнительных путях, чтобы достигнуть PEER_out. Каждое исследование собирает соответствующий внутридомен, направляющий информацию. Маршрутизатор выхода собирает информацию о каждом исследовании, включая маршрут внутридомена и хранит это в местном масштабе. После ожидания короткого периода времени информация о лучшем исследовании хранится в маршрутизаторе выхода наряду с областью пути, которая заполнена, используя путь, зарегистрированный лучшим исследованием. Это государство является переходным и смоется, если обратное резервирование пути не сделано вдоль этого сегмента пути. Последний маршрутизатор перелета выбирает лучшее исследование, полностью изменяет источник, направил путь, и начинает резервирование в обратном режиме. reserve_probe использует высокопоставленную информацию, поддержанную в полностью измененном исходном маршруте, чтобы достигнуть соответствующих всматривающихся узлов. Поиск таблицы сделан к таблице отображения подробно остановиться на пути внутридомена, позволяющем исследование зарезервировать ресурсы в пределах домена. Путь внутридомена не зарегистрирован в исследовании во время ни одного прохода, предотвратить КАК - чувствительная информация от того, чтобы быть показанным.
• Количественная обработка наверху: Чтобы оценить вычислительное наверху предвычисления для параллельного исследования, мы измерили время, чтобы найти дополнительные пути для данной исходной пары адресата для установки моделирования. На Sparc ультра60 серверов, время вычисления upto шесть непрерывных путей для единственного источника для всех возможных адресатов в наших 100 узлах многодоменная топология, составляют 178 мс. Масштабируя upto к 10 000 ASes, время вычисления - приблизительно 10 s. Выберите, что параллельное исследование полагается на статические метрики (счет перелета) для предвычисления и только требует, чтобы информация от всматривающейся перспективы ссылки была точна. Кроме того, мы полагаем, что всматривающиеся ссылки являются относительно более здравыми, чем регулярный внутридомен связывается из-за провайдеров денежно-кредитный стимул для того, чтобы поддержать ссылки, объединенные с избыточностью и потерпеть неудачу - по механизмам. Таким образом, мы не ожидаем, что предвычисление всматривающихся ссылок часто случится.

7. Связанная работа

В дополнение к работе, упомянутой в Разделе 2, было существенное количество предшествующего исследования относительно QoS, направляющего в пределах домена. Мы суммируем несколько из представительных схем ниже и исследуем сложность и проблемы масшабируемости, которые типично действуют как барьер к развертыванию. В частности мы сосредотачиваемся на многопутевых схемах маршрутизации, так как алгоритм СТР, предложенный в этой газете, является лучшим алгоритмом выполнения.

Также было существенное предшествующее исследование относительно многопутевой маршрутизации. Один такой подход предложен в [26] для трафика в реальном времени. В этой схеме исследования посылают на путях замены k, которые одновременно используют k метрики, такие как счет перелета, чтобы найти лучший путь. Исследования посылают между Промежуточными Адресатами (логин), которые являются подмножеством маршрутизаторов вдоль наименее пути стоимости. Каждое исследование резервирует ресурсы вдоль его пути. Из данного логина, первое исследование, которое достигнет следующих побед логина. Средства, сохраненные на другом k − 1 путь, высвобождены между логином. Процесс тогда повторен, пока адресат не достигнут. У этого протокола есть существенная сложность, поскольку это пытается оценить метрики замены k между логином. Кроме того, k исследует каждые запасные ресурсы на пути, эффективно блокирующем другие запросы на каждом из тех путей. Кроме того, в сети, где есть существенное совместное использование ссылок между дополнительными путями, ресурсы могут быть сохранены при общих ссылках для каждой из k метрик, создающих узкие места, которые увеличивают вероятность блокирования далее.

Касательно [27] предлагает распределенный механизм выбора маршрута для сообщений в реальном времени. Наводнения алгоритма, направляющие сообщения из источника к адресату. Каждое сообщение накапливает полную задержку пути, который был пересечен. Когда сообщение маршрутизации получено промежуточным узлом, сообщение отправлено только, когда одно из следующих двух условий удовлетворено: (1) сообщение является первым такое сообщение, полученное узлом, или (2), сообщение несет лучшую накопленную задержку чем ранее полученные сообщения. Если любое условие будет истинно, то сообщение будет отправлено вдоль уходящих ссылок при условии, что задержка на той уходящей ссылке, добавленной к накопленной задержке сообщения, не превышает непрерывное требование задержки. Эта схема посылает сообщения на 2 м., где м. является числом сетевых ссылок, которые могли стать существенным наверху для больших сетей. Каждое сообщение резервирует ресурсы, пока путь не отобран, который мог заблокировать другие сообщения. Кроме того, каждое сообщение резервирует ресурсы в передовом проходе, приводящем к блокированию последующих запросов резервирования.

Касательно [28] предлагает многопутевую маршрутизацию и комбинирует процесс маршрутизации и резервирования ресурса, посредством чего ресурсы сохранены на многократных путях, используя подход, подобный наводнению для того, чтобы найти дополнительные пути. Каждый узел поддерживает топологию сети и стоимость каждой ссылки. Когда узел желает установить подключение с определенными ограничениями QoS, он находит подграф сети, которая содержит ссылки, которые приводят к адресату с "разумной" стоимостью. Такой подграф называют diroute. Запросы резервирования затопляются вдоль выполнимых ссылок в diroute к адресату и резервируют ресурсы вдоль различных путей параллельно. Когда адресат получает сообщение резервирования, путь маршрутизации установлен. Варианты вышеупомянутой схемы предложены, чтобы уменьшить обмен между маршрутизацией времени и оптимальным выбором пути. Первое сообщение резервирования, которое достигнет адресата, решает путь. Это могло привести к подоптимальному пути, так как адресат только отвечает на первое сообщение. Эта схема резервирует ресурсы на многократных путях и страдает от тех же самых недостатков схемы, упомянутой выше [26]. Кроме того, из-за подхода наводнения, возможно, что узел, который не является частью отобранного пути, не знает, что был отобран выполнимый путь. В результате ресурсы могли излишне считаться в течение долгого времени периодом.

Касательно [29] предлагает отборное исследование ссылок как часть распределенного механизма маршрутизации, который делает отправление перелета перелетом. Идея здесь состоит в том, чтобы ограничить наводнение, только ускоряя исследования на тех ссылках, которые удовлетворяют QoS для данного потока. Каждый промежуточный узел способен к посылке исследований в этом подходе. Алгоритм находит путь вслепую через соревнование среди исследований, посредством чего первое исследование, достигающее адресата, побеждает. Это - подход перелета перелетом, посредством чего исследования могли следовать намного более длинным маршрутом, чтобы достигнуть адресата, так как у самого короткого пути может быть недостаточная способность.

Касательно [30] предлагает билет, базируемый, исследуя подход, который ограничивает число исследований, посланных специфическим узлом, и предназначается для основанной на задержке маршрутизации. Определенное число билетов выпущено в источнике согласно уровню утверждения сетевых ресурсов. Каждому исследованию назначают по крайней мере один билет, чтобы быть правильным и только исследует с билетами, отправлены. Это ограничивает число обысканных путей в целом, уменьшая количество затопляемых сообщений от предыдущего подхода. Алгоритм использует неточное государство в промежуточных узлах, чтобы вести исследования вдоль самого лучшего пути адресату. В то время как это уменьшает наводнение предыдущей схемы, оно все еще имеет существенный наверху. Схема также принимает глобальное государство, которое чревато неточностью из-за информации государства устаревшей ссылки.

Недавняя работа [19] добавляет расширение QoS к ПОГРАНИЧНОМУ МЕЖСЕТЕВОМУ ПРОТОКОЛУ, названному доступным индексом пропускной способности. Это предложение требует модификации ПОГРАНИЧНОГО МЕЖСЕТЕВОГО ПРОТОКОЛА, используя новое сообщение ОБНОВЛЕНИЯ ПОГРАНИЧНОГО МЕЖСЕТЕВОГО ПРОТОКОЛА. Исследование моделирования авторов на очень высоком уровне, где каждый домен обработан как единственный узел. Нет никакой оценки на объединенном воздействии, предают земле и маршрутизация внутридомена. В нашей деятельности мы предлагаем направить алгоритмы, которые не требуют изменений к ПОГРАНИЧНОМУ МЕЖСЕТЕВОМУ ПРОТОКОЛУ, и оценивают это использование спроектированной сети, моделируя и intra и пересечение междомена к как близко приблизительное поведение реального мира.

8. Заключения

В этой газете мы изучили работу различного QoS маршрутизация схем, которые покрывают широкий спектр от самой короткой маршрутизации пути до гибридных многопутевых схем маршрутизации. Эти алгоритмы допущены, используя оверлейную архитектуру сети, которая дает возможность равноправному информационному обмену государства ссылки быть распространенным, не полагаясь на изменения к существующим протоколам, таким как ПОГРАНИЧНЫЙ МЕЖСЕТЕВОЙ ПРОТОКОЛ. Архитектура также позволяет гибкую инъекцию метрик, которые могли использоваться для QoS, направляющего, включая доступную пропускную способность, и задержку, в зависимости от приложения. Мы оценили эти схемы на реалистическом ISP и междомене, направляющем топологию, у которой есть ссылки соответственно проставленные размеры ограничения трафика использования. Мы исчерпывающе исследовали обмен масшабируемости работы в этой газете и предложили алгоритмы, которые относятся и к окружающей среде междомена и внутридомена. Дополнительно, мы предложили детали выполнения, которые облегчат развертывание предложенных алгоритмов в реальных сетях.

Как часть будущей работы, мы воздействуем на оценку предложенных алгоритмов на реальном испытательном стенде, используя оверлейное программное обеспечение узла СПИННЫХ ХРЕБТОВ. СПИННЫЕ ХРЕБТЫ Накладывают узлы, исследуют друг друга, используя множество различных метрик и отправляют трафик, основанный на лучшем следующем перелете. Мы в настоящее время изменяем СПИННЫЕ ХРЕБТЫ, чтобы выполнить исходную маршрутизацию и оцениваем QoS маршрутизация алгоритмов, выполняя СПИННЫЕ ХРЕБТЫ по Emulab [31] испытательный стенд.



		Этот Документ


			SummaryPlus
			Полный Текст + Ссылки
			Изображения ·Thumbnail
			PDF (592 K)



		Действия


			Процитированный
			Сохраните как Предупреждение Цитаты
			Почтовая Статья
			Экспортная Цитата

Маршрутизация междомена: Алгоритмы для гарантий QoS

Резюме

Схема Статьи